﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Net;
using System.Text.RegularExpressions;
using System.IO;

namespace ProjectEulerSolutions
{
    /*
     * NOTE: This problem is a significantly more challenging version of Problem 81.

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

	
131	673	234	103	18
201	96	342	965	150
630	803	746	422	111
537	699	497	121	956
805	732	524	37	331
	

Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.

     * */
    class Problem83 : IProblem
    {
        int[] a = new int[]
        {
            131,	673,	234,	103,	18,
            201,	96,	    342,	965,	150,
            630,	803,	746,	422,	111,
            537,	699,	497,	121,	956,
            805,	732,	524,	37,	    331
        };


        public string Calculate()
        {
            //WebClient wc = new WebClient();
            //String input = wc.DownloadString("http://projecteuler.net/project/matrix.txt");

            String input = "";
            using (StreamReader sr = new StreamReader("Input\\matrix.txt"))
            {
                input = sr.ReadToEnd();
            }


            a = Regex.Matches(input, "[0-9]+").Cast<Match>().Select(x => int.Parse(x.Value)).ToArray();

            int n = (int)Math.Sqrt(a.Length);
            if (n != Math.Sqrt(a.Length))
                throw new ArgumentException();

            int[] b = new int[a.Length];

            b[0] = a[0]; //prvi
            for (int j = 1; j < n; j++)
            {
                b[n * j] = b[n * (j - 1)] + a[n * j]; //prethodni
            }

            for (int i = 1; i < n; i++)
            {
                bool changes = false; 
                for (int j = 0; j < n; j++)
                {
                    int value = a[i + n * j] + b[i - 1 + n * j]; //ovaj i onaj lijevo
                    if ((value < b[i + n * j]) || (b[i + n * j] == 0)) //veci je ili je unasinged
                    {
                        b[i + n * j] = value;

                        //od j prema gore
                        for (int k = j - 1; k >= 0; k--)
                        {
                            value = a[i + n * k] + b[i + n * (k + 1)]; //ovaj plus donji
                            if (value < b[i + n * k] || (b[i + n * k] == 0))
                            {
                                changes = true;
                                b[i + n * k] = value; //manji je pa ga stavimo
                            }
                            else
                            {
                                break; //nije manji pa netreba dalje trazit
                            }
                        }

                        //od j prema dole
                        for (int k = j + 1; k < n; k++)
                        {
                            value = a[i + n * k] + b[i + n * (k - 1)]; //ovaj plus gornji
                            if (value < b[i + n * k] || (b[i + n * k] == 0))
                            {
                                changes = true;
                                b[i + n * k] = value; //manji je pa ga stavimo
                            }
                            else
                            {
                                break; //nije manji pa netreba dalje trazit
                            }
                        }
                    }
                }

                //ako bude promjena vracat cemo se lijevo
                while (changes)
                {
                    changes = false;
                    for (int h = i - 1; h > 0; h--)
                    {
                        for (int j = 0; j < n; j++)
                        {
                            int value = a[h + n * j] + b[h + 1 + n * j]; //ovaj i onaj desno
                            if ((value < b[h + n * j]) || (b[h + n * j] == 0)) //veci je ili je unasinged
                            {
                                b[h + n * j] = value;

                                //od j prema gore
                                for (int k = j - 1; k >= 0; k--)
                                {
                                    value = a[h + n * k] + b[h + n * (k + 1)]; //ovaj plus donji
                                    if (value < b[h + n * k] || (b[h + n * k] == 0))
                                    {
                                        changes = true;
                                        b[h + n * k] = value; //manji je pa ga stavimo
                                    }
                                    else
                                    {
                                        break; //nije manji pa netreba dalje trazit
                                    }
                                }

                                //od j prema dole
                                for (int k = j + 1; k < n; k++)
                                {
                                    value = a[h + n * k] + b[h + n * (k - 1)]; //ovaj plus gornji
                                    if (value < b[h + n * k] || (b[h + n * k] == 0))
                                    {
                                        changes = true;
                                        b[h + n * k] = value; //manji je pa ga stavimo
                                    }
                                    else
                                    {
                                        break; //nije manji pa netreba dalje trazit
                                    }
                                }
                            }
                        }
                    }

                    //bilo je promjena ulijevo pa opet treba racunat i desno
                    if (changes)
                        i--;
                }
            }


            //for (int j = 0; j < n; j++)
            //{
            //    for (int i = 0; i < n; i++)
            //    {
            //        Console.Write(a[i + j * n] + " ");
            //    }
            //    Console.WriteLine();
            //}

            //Console.WriteLine();

            //for (int j = 0; j < n; j++)
            //{
            //    for (int i = 0; i < n; i++)
            //    {
            //        Console.Write(b[i + j * n] + " ");
            //    }
            //    Console.WriteLine();
            //}
            return b[b.Length - 1].ToString();
        }
    }
}
